今天是 Python 學習的第 26 天,實作的難度會稍微提升,會使用遞迴概念實作一個解決迷宮問題的演算法。迷宮問題是經典的回溯法應用,需要找到一條從起點到終點的路徑,且只能在允許的路徑 (0 代表之)上行走,不能穿越障礙物 (1 代表之)。這個問題的解法可以透過回溯法來實現,回溯法是一種嘗試錯誤的策略,當發現當前路徑不可行時,會回到之前的步驟,嘗試其他可能的方向。
定義迷宮地圖
使用一個二維列表表示迷宮,0 代表可以通行的路徑,1 代表障礙物。起點預設在左上角 (0, 0),終點在右下角 (4, 4)。
建立解決方案框架
建立一個遞迴函數來嘗試找到解決迷宮的路徑。solve_maze 函數會檢查當前位置是否有效,並使用遞迴探索所有可能的路徑,直到找到終點或無法前進為止。每次遞迴呼叫會嘗試向下、右、上、左方向移動。
呼叫函數進行求解
呼叫 solve_maze 函數,並檢查是否找到可行路徑,如果找到路徑,會輸出該路徑,若沒辦法找到就會提示無法找到路徑。
找到路徑: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]